#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int data;
    struct node *next;
}NODE;

void SetData(NODE **list, int data)
{
    (*list) = (NODE *)malloc(sizeof(NODE));
    (*list)->data = data;
    (*list)->next = NULL;
}

void ShowList(NODE *list)
{
    while (list != NULL && list->next != NULL) {
        printf("%d->", (list++)->data);
    }
    if (list != NULL) {
        printf("%d\n", list->data);
    }
}

void flod(NODE *list)
{
    // STEP1：找到链表的中间结点，1，2，3，4，5
    NODE *mid, *end;

    mid = end = list;
    while (end != NULL) {
        mid = mid->next;
        end = end->next;
        if (end != NULL) {
            end = end->next;
        }
    }
    // 结果：得到 mid 指向第 n/2+1 个结点，end 指向链表末尾结点

    // STEP2：将后半链表翻转
    NODE *temp, *curr, *newNext;
    
    curr = mid->next;           // curr 指向每次需要翻转的当前结点
    mid->next = NULL;           // 将前半段的末尾结点的 newNext 指针指向 NULL
    newNext = NULL;             // newNext 为当前结点的重设 newNext 结点
    while (curr != NULL) {
        temp = curr->next;      // temp 暂存当前结点的下一个结点
        curr->next = newNext;   // 当前结点的 newNext 为之前设置的 newNext
        newNext = curr;         // 下一个结点的 newNext 为当前结点
        curr = temp;            // 当前结点更新为上一结点的 newNext 结点
    }
    // 结果：curr 指向 NULL，next 指向 后半段链表倒转后的首结点
    
    // STEP3：使用 list 和 newNext 指针合并两个链表
    NODE *head = newNext;      // 重命名 newNext 为 head

    while (head != NULL) {
        temp = head->next;
        head->next = list->next;
        list->next = head;
        list = head->next;
        head = temp;
    }
}

int main(int argc, char const *argv[])
{
    NODE *list;

    SetData(&list, 1);
    SetData(&list->next, 2);
    SetData(&list->next->next, 3);
    SetData(&list->next->next->next, 4);
    SetData(&list->next->next->next->next, 5);

    ShowList(list);
    flod(list);
    ShowList(list);

    return 0;
}